// 给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

// 示例 1:

// 输入: [2,2,3,4]
// 输出: 3
// 解释:
// 有效的组合是: 
// 2,3,4 (使用第一个 2)
// 2,3,4 (使用第二个 2)
// 2,2,3
// 注意:

// 数组长度不超过1000。
// 数组里整数的范围为 [0, 1000]。

#include "./stdc++.h"

/* 枚举 - 超时
时间复杂度：O(N^3)
空间复杂度：O(1)
*/
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int res{0};
        int n = nums.size();
        for (int i{0}; i < n - 2; ++i) {
            for (int j{i + 1}; j < n - 1; ++j) {
                for (int k{j + 1}; k < n; ++k) {
                    if ( nums[i] + nums[j] > nums[k]
                      && nums[i] + nums[k] > nums[j]
                      && nums[j] + nums[k] > nums[i] ) {
                        ++res;
                    }
                }
            }
        }
        return res;
    }
};

/* 二分查找
时间复杂度：O(N^2 * logN)
空间复杂度：O(logN)
*/
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int res{0};
        for (int i{0}; i < n - 2; ++i) {
            int k = i + 2;
            for (int j{i + 1}; j < n - 1 && nums[i] != 0; ++j) {
                k = binarySerarch(nums, k, n - 1, nums[i] + nums[j]);
                res += k - j - 1;
            }
        }
        return res;
    }
private:
    int binarySerarch(vector<int>& nums, int l, int r, int x) {
        while (r >= l && r < nums.size()) {
            int mid = (l + r) / 2;
            if (nums[mid] >= x) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

/* 双指针
时间复杂度：O(N^2)
空间复杂度：O(logN)
*/
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int res{0};
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i{0}; i < n - 2; ++i) {
            if (nums[i] == 0) {
                continue;
            }
            int k{i + 2};
            for (int j{i + 1}; j < n - 1; ++j) {
                while (k < n && nums[k] < nums[i] + nums[j]) {
                    ++k;
                }
                res += k - 1 - j;
            }
        }
        return res;
    }
};

// 排序 + 二分
// 二分查找 []j+1,n-1]里面，找出最大的满足nums[k]<nums[i]+nums[j] 的下标 k
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int res{0};
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i{0}; i < n - 2; ++i) {
            for (int j{i + 1}; j < n - 1; ++j) {
                int left = j + 1;
                int right = n - 1;
                int k = j;
                while (left <= right) {
                    int mid = left + (right - left) / 2;
                    if (nums[mid] < nums[i] + nums[j]) {
                        k = mid;
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                res += k - j;
            }
        }
        return res;
    }
};

